package day2_linkedlist.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author: yuisama
 * @Date: 2021/9/2 14:38
 * @Description:相交链表
 * https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
 */
public class Num160 {
    // 方法1.哈希表法
    // 先遍历链表A。将所有节点存储在哈希表中
    // 再遍历链表B，当发现遍历过程中有节点在哈希表中，则此节点即为相交节点
//    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        Set<ListNode> nodeSet = new HashSet<>();
//        ListNode temp = headA;
//        while (temp != null) {
//            nodeSet.add(temp);
//            temp = temp.next;
//        }
//        // 再遍历链表B
//        temp = headB;
//        while (temp != null) {
//            if (nodeSet.contains(temp))
//                return temp;
//            temp = temp.next;
//        }
//        // 走完链表B发现还是没有相同节点，两个链表不相交
//        return null;
//    }
    // 双指针法
    // 假设两个相交链表A，B长度分别 a+c=m,b+c=n
    // 当a,b相等时，则同时遍历两个链表会同时到达相交节点
    // 当a,b不相等时，让两个链表分别各自遍历，
    // 当到达终点时再从对方链表头出发在走一次，则此时两个指针一定同时到达相交节点
    // a+c+b=b+c+a
    // 若两个链表不相交，则走完对方链表后同时到达终点null
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null)
            return null;
        ListNode pA = headA;
        ListNode pB = headB;
        // 终止条件为pA是否与pB相等，相交链表返回相交节点，不相交同时到达null
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}
